package weekMatch.two_106;

import jdk.nashorn.internal.ir.IfNode;

import java.net.IDN;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class LeeCode_03 {
    public static void main(String[] args) {
        System.out.println(sumDistance2(new int[]{-2, 0, 2}, "RLL", 3));
        System.out.println(sumDistance2(new int[]{1, 0}, "RL", 2));
        System.out.println(sumDistance2(new int[]{-10,-13,10,14,11}, "LRLLR", 2));
    }
    private static int sumDistance2(int[] nums_, String S, int d) {
        long mod = (long) (1e9 + 7);
        char[] s = S.toCharArray();
        int n = S.length();
        long[] nums = new long[n];
        for (int i = 0; i < n; i++) {
            nums[i] = nums_[i];
        }
        for (int i = 0; i < n; i++) {
            if(s[i] == 'R'){
                nums[i] += d;
            }else {
                nums[i] -= d;
            }
        }
        Arrays.sort(nums);
        long[] sums = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        long[] ans = new long[n];
        for (int i = 1; i < n; i++) {
            ans[i] = nums[i] * i - sums[i];
            ans[i] %= mod;
            ans[i] += ans[i - 1];
            ans[i] %= mod;
        }
        return (int) ans[n - 1];
    }
    private static int sumDistance(int[] nums_, String S, int d) {
        long mod = (long) (1e9 + 7);
        char[] s = S.toCharArray();
        int n = S.length();
        long[] nums = new long[n];
        for (int i = 0; i < n; i++) {
            nums[i] = nums_[i];
        }
        Integer[] is = new Integer[n];
        for (int i = 0; i < n; i++) {
            is[i] = i;
        }
        Arrays.sort(is, Comparator.comparingLong(o -> nums[o]));
        for (int i = 0; i < n; i++) {
            s[i] = S.charAt(is[i]);
        }
        Arrays.sort(nums);
        PriorityQueue<long[]> queue = new PriorityQueue<>(Comparator.comparingLong(o -> o[1]));
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == 'R' && s[i + 1] == 'L'){
                queue.add(new long[]{i, nums[i + 1] - nums[i]});
            }
        }
        int[] remain = new int[n];
        Arrays.fill(remain, d);
        while (!queue.isEmpty()){
            long[] p = queue.poll();
            int index = (int) p[0];
            long l = nums[index], r = nums[index + 1];
            long cha = r - l;
            int pass = (int) (cha / 2);
            long nl, nr;
            if ((cha & 1) == 1)
                pass++;
            if (pass > remain[index] && pass > remain[index + 1]){
                break;
            }
            if ((cha & 1) == 1){
                nl = nums[index] + cha / 2;
                nr = nl + 1;
            }else {
                nl = nums[index] + cha / 2;
                nr = nl;
            }
            remain[index] -= pass;
            remain[index + 1] -= pass;
            s[index] = 'L';
            s[index + 1] = 'R';
            nums[index] = (int) nl;
            nums[index + 1] = (int) nr;
            if (index > 0 && s[index - 1] == 'R'){
                nums[index - 1] += pass;
                remain[index - 1] -= pass;
                queue.add(new long[]{index - 1, nums[index] - nums[index - 1]});
            }
            if (index + 2 < n && s[index + 2] == 'L'){
                nums[index + 2] -= pass;
                remain[index + 2] -=pass;
                queue.add(new long[]{index + 1, nums[index + 2] - nums[index + 1]});
            }
        }
        for (int i = 0; i < n; i++) {
            if (s[i] == 'L'){
                nums[i] -= remain[i];
            }else {
                nums[i] += remain[i];
            }
        }
        long[] tmp = new long[n];
        for (int i = 1; i < n; i++) {
            tmp[i] = tmp[i - 1] + nums[i] - nums[i - 1];
        }
        long[] sums = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + tmp[i - 1];
        }
        long[] ans = new long[n];
        for (int i = 1; i < n; i++) {
            ans[i] = tmp[i] * i - sums[i];
            ans[i] %= mod;
            ans[i] += ans[i - 1];
            ans[i] %= mod;
        }
        return (int) ans[n - 1];
    }
}